package net.tp.algo.flow;


/**
 * 
 * <p>Baseball Elimination problem.</p>
 * 
 * 
 * <pre>
 *                 w[i] l[i] r[i]        g[i][j]
 * i  team         wins loss left   Atl Phi NY  Mon
 * ------------------------------------------------
 * 0  Atlanta       90   61    11    -   1   6   4
 * 1  Philadelphia  88   68     6    1   -   1   4
 * 2  New York      87   64    11    6   1   -   4
 * 3  Montreal      79   71    12    4   4   4   -
 * </pre>
 * 
 * <p>Objective: determine if Montreal is mathematically eliminated? The maximum wins that Montreal can achieve is
 * $m = w_3 + r_3 = 79 + 12 = 91$. We need to determine if we can find a combination of win-loss among 4 teams
 * for all the remaining games such that each team has at most m wins in total. If such a combination exists,
 * then Montreal has a chance of being first (or tie in the first place). If we cannot find such a combination,
 * then it means that every combination of win-loss, there must exist a team that has more than m wins in total,
 * making Montreal eliminated mathematically.</p>
 * 
 * <p>To find if there exists a combination such that each team has at most m wins, we need to build a network
 * flow as follow:</p>
 * <ul>
 *  <li>Two nodes source $s$ and target $t$ are added.</li>
 * 	<li>Each pair of team that still has remaining game (i.e. $g_{ij} &gt; 0$) forms a node $v_{ij}$.</li>
 *  <li>Each team forms a node $v_i$.</li>
 *  <li>Add edge $(s, v_{ij})$ with capacity of $g_{ij}$.</li>
 *  <li>Add edge $(v_{ij}, v_i)$ and $(v_{ij}, v_j)$ with capacity of ∞. These edges are to simulate if team i or j will
 *  win for each game.</li>
 *  <li>Add edge $(v_i, t)$ with capacity of $m - w_i$. (this condition is important, it makes sure that
 *  each team, the remaining wins do not exceed $m-w_i$, or the total number of wins does not exceed $m$. Also note that
 *  we assume $m-w_i≥0$, otherwise, Montreal would surely be eliminated because there exists a team that has the current
 *  wins $w_i &gt; m$.)</li>
 * </ul>
 *
 * <p class="svg">
 * {@code
 * <svg width="443" height="292"><style>text {font-size:14px;font-style:normal;font-variant:normal;font-weight:bold;font-stretch:normal;text-align:start;line-height:125%;letter-spacing:0px;word-spacing:0px;writing-mode:lr-tb;text-anchor:start;fill:#000000;fill-opacity:1;stroke:none;font-family:Courier New;-inkscape-font-specification:Courier New Bold;}</style><defs id="defs4115"><marker refX="0" refY="0" orient="auto" id="Arrow1Mend" style="overflow:visible"><path d="M 0,0 5,-5 -12.5,0 5,5 0,0 z" transform="matrix(-0.4,0,0,-0.4,-4,0)" id="path4862" style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none" /></marker><marker refX="0" refY="0" orient="auto" id="Arrow2Lend" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="matrix(-1.1,0,0,-1.1,-1.1,0)" id="path4874" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" /></marker><marker refX="0" refY="0" orient="auto" id="Arrow2Lstart" style="overflow:visible"><path d="M 8.7185878,4.0337352 -2.2072895,0.01601326 8.7185884,-4.0017078 c -1.7454984,2.3720609 -1.7354408,5.6174519 -6e-7,8.035443 z" transform="matrix(1.1,0,0,1.1,1.1,0)" id="path4871" style="font-size:12px;fill-rule:evenodd;stroke-width:0.625;stroke-linejoin:round" /></marker></defs><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,0)" id="path4121" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,43.016663)" id="path4123" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,86.033325)" id="path4125" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,129.04999)" id="path4127" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,172.06665)" id="path4129" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(1,215.08331)" id="path4131" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(131.5,45.416655)" id="path4133" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(131.5,86.833346)" id="path4135" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(131.5,128.24996)" id="path4137" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(131.5,169.66665)" id="path4139" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(-120.5,107.54165)" id="path4143" style="fill:none;stroke:#000000" /><path d="m 180,38.862183 a 18.5,18.5 0 1 1 -37,0 18.5,18.5 0 1 1 37,0 z" transform="translate(247.5,107.54165)" id="path4145" style="fill:none;stroke:#000000" /><path d="M 274.93625,76.903571 181,45.362183 276.54139,114.90357" id="path4173" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><path d="M 143,42.362183 53.082776,131.96732" id="path4246" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="M 144,89.362183 56,136.36218" id="path4248" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="M 142.85347,128.36218 60,144.36218" id="path4250" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="m 143,168.36218 -84,-18" id="path4252" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="M 143.08278,205.67426 57.541388,154.90357" id="path4254" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="m 311,89.362183 80.08278,47.770687" id="path4258" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow2Lend)" /><path d="M 311.60514,126.73802 389,143.36218" id="path4260" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Lend)" /><path d="m 311.54139,167.42593 77.45861,-17" id="path4262" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Lend)" /><path d="m 310.85347,203.82079 80.60514,-47.24833" id="path4264" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow2Lend)" /><text x="149.89795" y="43.295288" id="text4266" xml:space="preserve" ><tspan x="149.89795" y="43.295288" id="tspan4268">0-1</tspan></text><text x="149.96289" y="86.311951" id="text4270" xml:space="preserve" ><tspan x="149.96289" y="86.311951" id="tspan4272">0-2</tspan></text><text x="149.8125" y="129.32861" id="text4274" xml:space="preserve" ><tspan x="149.8125" y="129.32861" id="tspan4276">0-3</tspan></text><text x="149.80908" y="215.36194" id="text4278" xml:space="preserve" ><tspan x="149.80908" y="215.36194" id="tspan4280">1-3</tspan></text><text x="149.95947" y="172.44781" id="text4282" xml:space="preserve" ><tspan x="149.95947" y="172.44781" id="tspan4284">1-2</tspan></text><text x="150.01074" y="258.3786" id="text4286" xml:space="preserve" ><tspan x="150.01074" y="258.3786" id="tspan4288">2-3</tspan></text><text x="288.7959" y="88.711945" id="text4290" xml:space="preserve" ><tspan x="288.7959" y="88.711945" id="tspan4292">0</tspan></text><text x="288.78906" y="130.23117" id="text4294" xml:space="preserve" ><tspan x="288.78906" y="130.23117" id="tspan4296">1</tspan></text><text x="289.05566" y="171.64778" id="text4298" xml:space="preserve" ><tspan x="289.05566" y="171.64778" id="tspan4300">2</tspan></text><text x="288.81982" y="212.96194" id="text4302" xml:space="preserve" ><tspan x="288.81982" y="212.96194" id="tspan4304">3</tspan></text><text x="36.778809" y="149.48685" id="text4306" xml:space="preserve" ><tspan x="36.778809" y="149.48685" id="tspan4308">s</tspan></text><text x="404.3584" y="150.49515" id="text4310" xml:space="preserve" ><tspan x="404.3584" y="150.49515" id="tspan4312">t</tspan></text><text x="109.42822" y="66.362183" id="text4318" xml:space="preserve" ><tspan x="109.42822" y="66.362183" id="tspan4320">1</tspan></text><text x="109.11035" y="100.36218" id="text4322" xml:space="preserve" ><tspan x="109.11035" y="100.36218" id="tspan4324">6</tspan></text><text x="109.55469" y="128.36218" id="text4326" xml:space="preserve" ><tspan x="109.55469" y="128.36218" id="tspan4328">4</tspan></text><text x="109.42822" y="158.36218" id="text4330" xml:space="preserve" ><tspan x="109.42822" y="158.36218" id="tspan4332">1</tspan></text><text x="109.55469" y="184.36218" id="text4334" xml:space="preserve" ><tspan x="109.55469" y="184.36218" id="tspan4336">4</tspan></text><text x="109.55469" y="211.36218" id="text4338" xml:space="preserve" ><tspan x="109.55469" y="211.36218" id="tspan4340">4</tspan></text><path d="M 144.91722,244.0501 54,159.36218" id="path9762" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart)" /><path d="m 274,84.362183 -93,-2 95,74.999997" id="path11082" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><path d="m 275,92.36218 -95,30 95.29306,77.45861" id="path11086" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><path d="M 273.91722,130.90357 181,162.36218 l 92,4" id="path11840" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><path d="M 277.31208,138.0501 180,203.36218 l 93.16555,1.77069" id="path11842" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><path d="M 274.54139,174.0501 181,245.36218 l 95,-27" id="path11844" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:url(#Arrow2Lstart);marker-end:url(#Arrow2Lend)" /><text x="232" y="62.362183" id="text13524" xml:space="preserve" ><tspan x="232" y="62.362183" id="tspan13526">∞</tspan></text><text x="331.78091" y="94.362183" id="text13528" xml:space="preserve" ><tspan x="331.78091" y="94.362183" id="tspan13530">1</tspan></text><text x="331.81168" y="127.95648" id="text13532" xml:space="preserve" ><tspan x="331.81168" y="127.95648" id="tspan13544">3</tspan></text><text x="331.90738" y="157.25363" id="text13536" xml:space="preserve" ><tspan x="331.90738" y="157.25363" id="tspan13546">4</tspan></text><text x="327.64859" y="182.30791" id="text13540" xml:space="preserve" ><tspan x="327.64859" y="182.30791" id="tspan13548">12</tspan></text><text x="55.128902" y="62.636265" id="text14689" xml:space="preserve" ><tspan x="55.128902" y="62.636265" id="tspan14691">g<tspan id="tspan14693" style="font-size:65.00091553%;baseline-shift:sub">ij</tspan></tspan></text><path d="M 78.477612,58.744815 105.0692,60.690541" id="path14703" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-start:none;marker-end:url(#Arrow1Mend)" /><text x="378.11942" y="89.876427" id="text15781" xml:space="preserve" ><tspan x="378.11942" y="89.876427" id="tspan15783">m-w<tspan id="tspan15785" style="font-size:65.00091553%;baseline-shift:sub">i</tspan></tspan></text><path d="m 372.28223,85.984978 -29.18589,3.242877" id="path15787" style="fill:none;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Mend)" /></svg>
 * }
 * </p>
 *
 * 
 * 
 * @author Trung Phan
 *
 */
public class BaseballElimination {

	
	
	
	
	
}
